package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author qezhhnjy
 * @date 2020/12/20-22:17
 *
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。
 *（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 */
public class BinaryTreeLevelTraversal {
    public List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        Collections.reverse(result);
        return result;
    }

    private void dfs(TreeNode root, int i) {
        if (root == null) return;
        if (result.size() == i) {
            result.add(new ArrayList<>());
        }
        result.get(i).add(root.val);
        dfs(root.left, i + 1);
        dfs(root.right, i + 1);
    }}
